package com.acwing.partition6;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/11 9:53
 */
public class AC523组合数问题 {

    private static final int N = 2010;
    private static int[][] c = new int[N][N], s = new int[N][N];
    private static int n, m, k;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int t = Integer.parseInt(ss[0]);
        k = Integer.parseInt(ss[1]);
        //预处理出所有的组合数
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) c[i][j] = 1;
                else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % k;
                if (c[i][j] == 0) {
                    //说明当前组合数是k的倍数
                    s[i][j] = 1;
                }
            }
        }
        //预处理二维前缀和
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }
        while (t-- > 0) {
            ss = reader.readLine().split(" ");
            n = Integer.parseInt(ss[0]);
            m = Integer.parseInt(ss[1]);
            writer.write(s[n][m] + "\n");
        }
        writer.flush();
    }
}
